% Chapter 1

\chapter*{Introducción} % Write in your own chapter title
\label{Intro}
\lhead{\emph{Introducción}} % Write in your own chapter title to set the page header
\addcontentsline{toc}{chapter}{Introducción}
% Descripción general
En Ciencias de la Computación se entiende por \textbf{problemas de decisión}
los problemas en los que se plantea una pregunta en un sistema formal sobre una entrada
arbitraria, cuya respuesta puede ser afirmativa o negativa.
Los problemas de decisión son interesantes porque permiten modelar y razonar
sobre aplicaciones reales. Por ejemplo, el problema de decisión de
$k$-colorabilidad pregunta si los vértices de un grafo pueden ser coloreados
con $k$ colores distintos, de modo de que a ningún par de vértices conectados
por una arista se les asigne el mismo color . En un compilador, la tarea de
asignar los valores frecuentemente utilizados a registros para
mejorar la eficiencia del código generado puede modelarse con un problema de
$k$-colorabilidad: los vértices del grafo son las variables, y si dos variables
se necesitan al mismo tiempo se coloca un arco entre ellas. Al encontrar una
forma de colorear este grafo con $k$ colores se ha hallado una forma de
utilizar $k$ registros distintos para almacenar las variables.

Los problemas de decisión pueden agruparse en distintas clases según su
complejidad. Una importante clase de complejidad es NP (siglas de
\textit{Nondeterministic Polynomial time}), a la cual pertenecen problemas
interesantes como $k$-colorabilidad, satisfacibilidad proposicional
(\textbf{SAT}) y hallar un camino \textit{hamiltoniano} en un grafo. Otra clase
más general de problemas de interés para este trabajo es PH (\textit{Polynomial Hierarchy}),
que incluye problemas computacionalmente más complejos como formas restringidas de
\textit{Quantified Boolean Formula} (QBF).

El área de investigación de planificación automática estudia una forma general
de resolución de problemas utilizando \textbf{planes}. Un problema de planificación
consiste de un estado inicial, un conjunto de estados finales y un conjunto de
acciones posibles. Luego, la tarea del \textbf{planificador} 
consiste en encontrar una secuencia de acciones que conduzca
el estado inicial hasta un estado final, o determinar que tal secuencia de
acciones no existe.

Este trabajo se enfoca en el desarrollo de una herramienta que permite
\textbf{reducir} un problema de
decisión perteneciente a las clases NP o PH codificado en lógica de segundo orden,
a un problema de planificación automática. 
La motivación para realizar esta herramienta es que
existen planificadores muy eficientes, pero no es trivial
expresar un problema de decisión cualquiera en términos de estado inicial,
estados finales y acciones, como lo requieren los
planificadores. A veces, la utilización de un lenguaje declarativo es una forma
más concreta y directa para la descripción de un problema de decisión en
particular. En estos casos, es preferible modelarlo en un lenguaje de más alto
nivel y que la herramienta lo reduzca a un formato de entrada aceptado por
los planificadores, los cuales pueden proceder entonces a computar su solución.

% Trabajos anteriores
Otros autores ya han utilizado fragmentos de la lógica de segundo orden como un lenguaje de
programación declarativo. En la obra de \cite{reiter:cwa} se describe un
lenguaje de reglas y consultas a bases de datos que es un subconjunto de
PROLOG, llamado DATALOG. A su vez, \cite{cadoli:npspec} presentan una
extensión de este lenguaje que permite la codificación de problemas NP y
se desarrolla un método para compilar los problemas a código de PROLOG, el cual
fue probado con pequeñas instancias del \textbf{problema de la mochila}
(\textit{knapsack problem}) y el \textbf{problema del viajante}
(\textit{traveling salesman problem}).

\cite{mitchell:npsearch} proponen, por su parte, el lenguaje de
Extensión de Modelos (MX), que es conceptualmente muy cercano a la lógica de
segundo orden. Este trabajo se enfoca en la descripción formal del lenguaje y
en discutir la posibilidad de diseñar un solucionador. En esta sección, los
autores aconsejan la realización de una traducción a otro lenguaje para el cual
existan solucionadores: es precisamente esto lo que se ha hecho en el presente
trabajo con la función que traduce descripciones declarativas a problemas
de planificación, área para la cual existe una amplia variedad de solucionadores.

Otro trabajo relacionado a este proyecto es el de \cite{cadoli:safedelay}. Los
autores presentan una manera de razonar sobre los problemas de
decisión, intentando reformularlos para hacerlos más fáciles de resolver. Se
utilizan sistemas especializados para la modelación de restricciones y
solucionadores provenientes de muchos sub-campos de la Inteligencia Artificial.
Sin embargo, dependiendo del solucionador, se podría requerir que la fórmula
declarativa a solucionar esté en un formato particular, lo cual no es tan
conveniente como el enfoque ``independiente del dominio'' que provee la
planificación automática.

El objetivo general del proyecto es permitir la resolución de problemas
NP y de la jerarquía polinomial (PH) expresados a través de un lenguaje declarativo basado en 
la lógica de segundo orden.  Así, problemas cuya aplicación es
ampliamente conocida en Ciencias de la Computación podrán ser expresados
en un lenguaje conciso y ser resueltos sin la intervención del usuario luego de
la fase de modelación.

A fin de lograr el objetivo general, se plantean las siguientes metas
específicas:
\begin{itemize}
\item El desarrollo de una herramienta que procese la descripción lógica de un problema 
en NP o PH y genere automáticamente un problema de planificación equivalente 
formulado en el lenguaje PDDL (\textit{Planning Domain Definition Language}),
de uso estándar en la comunidad de planificación automática.
\item Una interfaz \textit{web} para este sistema que permita un acceso flexible
y rápido al traductor.
\end{itemize}

% Organización
Este trabajo está dividido en cinco capítulos. El primer capítulo aporta las
bases teórica sobre la que está fundamentada la traducción, incluyendo una
introducción a las áreas de planificación automática y complejidad descriptiva.
En el segundo capítulo se describe el lenguaje lógico diseñado para la
formulación de problemas a alto nivel, se presenta una reducción base del
fragmento de la lógica de segundo orden que captura a la clase NP
al lenguaje PDDL y se demuestran las propiedades formales de esta
traducción. 
%En el capítulo 3 se discuten algunas optimizaciones aplicadas sobre
%la función de reducción que permiten la generación de problemas de
%planificación menos complejos sin alterar las propiedades formales básicas de
%la traducción a NP. 
El capítulo 3 presenta una extensión de la herramienta que
permite traducir problemas más generales, pertenecientes a la jerarquía
polinomial.
El capítulo 4 trata sobre cómo fueron diseñados y llevados a
cabo experimentos sobre diferentes problemas en NP y PH traducidos con la herramienta,
además de ofrecer una discusión de los resultados obtenidos. Finalmente, el
capítulo 5 contiene conclusiones e ideas para trabajos
futuros.

Parte de este trabajo ha sido publicado en la \textit{21st International Conference on
Automated Planning and Scheduling} (ICAPS 2011;
\citeauthor{porco:npreductions}), y
enviado como artículo de investigación a la \textit{23rd International
Conference on Automated Planning and Scheduling} (ICAPS 2013).

%2. ACTIVIDADES QUE INVOLUCRA EL PROYECTO: 
%a. Investigación sobre el material teórico que permiten relacionar la teoría de complejidad computacional con complejidad descriptiva (lógica)
%b. Especificación del lenguaje lógico propuesto para realizar formulaciones, gramática y semántica de las construcciones
%c. Definición de la traducción del lenguaje lógico a PDDL, demostración de la correctitud y completitud de esta equivalencia
%d. Desarrollo del analizador léxico y sintáctico que permita reconocer este lenguaje
%e. Implementación de algoritmos para el post-procesamiento del árbol sintáctico para la simplificación de la fórmula lógica a formas canónicas
%f. Implementación de la traducción definida anteriormente sobre el árbol sintáctico de la fórmula procesada
%g. Evaluación experimental del desempeño de planificadores (del estado del arte) sobre fórmulas que corresponden a varios dominios
%h. Programación de una herramienta integral web que sirva como una interfaz ante el usuario para acceder al sistema de traducción de forma cómoda
%
%3. PUNTOS DE INTERÉS QUE HAN DE SER TRATADOS DURANTE LA EJECUCIÓN DEL PROYECTO:
%a. Teoría de complejidad descriptiva
%b. Equivalencia entre clases de complejidad y fragmentos del lenguaje PDDL
%c. Traducciones válidas entre fórmulas lógicas y dominios de planificación, optimización de las traducciones para su resolución con planificadores actuales
